package com.zhugang.week10;

/**
 * @program algorithms
 * @description: rob3
 * @author: chanzhugang
 * @create: 2022/08/30 17:49
 */
public class Rob3 {

    /**
     * 337 打家劫舍III
     *
     * @param root
     * @return
     */
    public int rob3(TreeNode root) {
        // 树形dp
        /**
         * 1、树形dp基于树结构推导，从下往上推，一般都是基于后序遍历
         * 2、money[0]:不偷此节点，当下最大金额；money[1]:偷此节点，当下最大金额
         * 3、root.money[0] = max(left.money[0], left.money[1]) + max(right.money[0], right.money[1])
         * root.money[1] = left.money[0] + right.money[0] + root.val
         */
        int[] money = postorder(root);
        // 偷或者不偷取最大值
        return Math.max(money[0], money[1]);
    }

    private int[] postorder(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] leftMoney = postorder(root.left);
        int[] rightMoney = postorder(root.right);
        int[] money = new int[2];
        // 不偷： 左右儿子偷或者不偷的最大值和
        money[0] = Math.max(leftMoney[0], leftMoney[1]) + Math.max(rightMoney[0], rightMoney[1]);
        // 偷： 做儿子不偷 与右儿子不偷
        money[1] = leftMoney[0] + rightMoney[0] + root.val;
        return money;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}